//
//  HeapSort.swift
//  ArithmeticClass15
//
//  Created by xiangzuhua on 2020/12/16.
//

import UIKit

class HeapSort: NSObject {
    var a: [Int] // 存储数据的数组
    var n: Int // 堆的空间大小
    var count: Int // 对重存储的数据个数
    init(_ capacity:Int) {
        a = [Int](repeating: 0, count: capacity + 1)
        n = capacity
        count = 0
    }
    //
    
    /// 建堆 - 方法一，每次取源数组中的一个数，插入到堆的末尾（第一次插入角标为1），
    /// 然后调用从下往上堆化的方法来将此数据做堆化处理，依次循环操作下去，直到源数组中的数据都取一遍为止。
    /// 这样就得到了一个已堆化的数组。
    /// - Parameter arr: 需要堆化的数组
    /// - Returns: 返回堆化过后的HeapSort对象
    class func create(fromFirst arr:[Int]) -> HeapSort{
        let heap = HeapSort.init(arr.count)
        var i = 0
        let number = arr.count // 遍历次数
        
        while i < number {
            i += 1
            heap.a[i] = arr[i-1]
            headify(fromBottom: i, heap: &heap.a)
        }
        
        return heap
    }
    
    /// 建堆 - 方法二，堆化数组从下标1开始存储源数组，然后从最后一个非叶子节点（完全二叉树n/2 ~n都是叶子节点）开始对该节点从上往下堆化，依次往上知道下标为1的节点堆化完成。
    /// - Parameter arr: 源数组
    /// - Returns: 返回已堆化的对象
    class func create(fromBack arr: [Int]) -> HeapSort{
        let heap = HeapSort.init(arr.count)
        heap.a = [0] + arr
        heap.count = arr.count
        var i = heap.n / 2
        while i > 0 {
            heapify(fromTop: i, heap: &heap.a, capacity: heap.n)
            i -= 1
        }
        return heap
    }
    
    
    public init(from arr:[Int]) {
        a = [0] + arr
        n = arr.count
        count = arr.count
        
    }
    
    // 往堆中插入值
    func insert(_ data:Int){
        if count > n {
            return
        }
        
        count += 1
        a[count] = data
        HeapSort.headify(fromBottom: count, heap: &a)
    }
    
    // 删除堆顶元素
    func deletTop() {
        if count <= 0 {
            return
        }
        
        a[1] = a[count]
        a.remove(at: count)
        count -= 1
        HeapSort.heapify(fromTop: 1, heap: &a, capacity: n)
    }
    
    
    /// 对堆进行排序，前提是数组已经堆化，这里默认对数组是从下标1开始
    /// - Parameter heapArr: 堆化后的数组
    /// - Returns: 返回排序后的数组
    func sort(){
        // 取堆顶的节点与最后一个叶子节点交换，
        var i = count
        while i > 1 {
            let temp = a[i]
            a[i] = a[1]
            a[1] = temp
            i -= 1
            HeapSort.heapify(fromTop: 1, heap: &a, capacity: i)
        }
    }
    
    /// 大顶堆的从上往下堆化
    /// - Parameters:
    ///   - index: 要堆化数据的下标
    ///   - heap: 做堆化处理的数组
    ///   - capacity: 数组中有效数据的个数
    class func heapify(fromTop index: Int, heap: inout [Int], capacity: Int) {
        var i = index
        var maxPos = i
        while true  {
            if 2 * i <= capacity && heap[2 * i] >= heap[i] {
                maxPos = 2 * i
            }
            if 2 * i + 1 <= capacity && heap[2 * i + 1] >= heap[maxPos]{
                maxPos = 2 * i + 1
            }
            if i == maxPos {// 比自己的子节点大，或者没有子节点了
                break
            }
            // 交换
            let temp = heap[i]
            heap[i] = heap[maxPos]
            heap[maxPos] = temp
            i = maxPos
        }
    }
    
    
    /// 大顶堆的从下往上堆化
    /// - Parameters:
    ///   - index: 数组中要往上堆化的数值的下标
    ///   - heap: 要堆化的数组
    class func headify(fromBottom index: Int, heap: inout [Int]) {
        var i = index
        // i会根据除以2的节奏变小，但是i必须大于1，这样i/2就不会等于0 ，数组中0下标对应的位置，不存数据。
        while i / 2 > 0 && heap[i] > heap[i / 2] {
            let temp = heap[i]
            heap[i] = heap[i / 2]
            heap[i / 2] = temp
            i = i / 2
        }
    }
}
// MARK:堆的应用 --- 优先级队列
extension HeapSort {
    /// n个有序(升序)数组合并成一个有序数组
    class func merge(manyOrderlyArr arrs:[[HeapNode]]) -> [HeapNode]{
        var resultArr = [HeapNode]()
        // 从各子数组中取最小的元素放入一个小顶堆(小顶堆的数组从下标1开始)
        var minTopHeapArr = [HeapNode]()
        let firstNode = HeapNode(-1, flag: -1, index: 0)
        minTopHeapArr.insert(firstNode, at: 0)
        for (index, arr) in arrs.enumerated() {
            minTopHeapArr.insert(arr[0], at: index + 1)
            minTopHeadify(fromBottom: index + 1, heap: &minTopHeapArr)
        }
        // 取到小顶堆的堆顶，存入大数组，然后从堆顶删除
        var tempMinNode = minTopHeapArr[1]
        resultArr.append(tempMinNode)
        minTopHeapArr.remove(at: 1)
        var i = 0
        while i < arrs.count {
            /// 没有超过边界，取值
            if tempMinNode.index + 1 < arrs[tempMinNode.flag].count {
                tempMinNode = arrs[tempMinNode.flag][tempMinNode.index + 1]
                minTopHeapArr.insert(tempMinNode, at: 1)/// 往堆顶插入一个值
                /// 堆化
                minTopHeapify(fromTop: 1, heap: &minTopHeapArr, capacity: minTopHeapArr.count - 1)
                // 取到小顶堆的堆顶，存入大数组，然后从堆顶删除
                tempMinNode = minTopHeapArr[1]
                resultArr.append(tempMinNode)
                minTopHeapArr.remove(at: 1)
            } else {
                tempMinNode = minTopHeapArr[2].value > minTopHeapArr[3].value ? minTopHeapArr[3] : minTopHeapArr[2]
                i += 1
            }
        }
        return resultArr
    }
    
    /// 高性能定时器
    ///传入一个存储了各个事件的时间戳的数组，返回一个最近要触发事件的时间，拿到这个时间与当前时间相减得到的差值就是定时器的时间间隔，不需要定时器每隔1s扫描一次
    /// - Parameter timeArr:存储时间戳的数组
    /// - Returns: 返回最近要触发的事件的时间
    class func efficientTimer(triggerTime timeArr:inout [HeapNode]) -> HeapNode?{
        // 对数组建堆
        create(fromFirst: &timeArr)
        
        // 取当前时间
        let currentTimeInterval = Date.init(timeIntervalSinceNow: 0).timeIntervalSince1970
        let currentTimeValue = Int(currentTimeInterval)
        // 当前时间与堆顶对比
        var result:HeapNode? = nil
        if timeArr[1].value > currentTimeValue {// 时间间隔是正数
            result = timeArr[1]// 取到堆顶
            deletTop(&timeArr)// 删除堆顶
            
        }else {// 时间间隔为负，堆顶的元素无效，已过期
            deletTop(&timeArr)// 删除堆顶
            if timeArr.count > 1 {// 如果堆中还有元素
                result = timeArr[1]
                deletTop(&timeArr)
            }
        }
        return result
        
    }
    
    /// 小顶堆的从下往上堆化
    /// - Parameters:
    ///   - index: 数组中要往上堆化的数值的下标
    ///   - heap: 要堆化的数组
    class func minTopHeadify(fromBottom index: Int, heap: inout [HeapNode]) {
        var i = index
        // i会根据除以2的节奏变小，但是i必须大于1，这样i/2就不会等于0 ，数组中0下标对应的位置，不存数据。
        while i / 2 > 0 && heap[i].value < heap[i / 2].value {
            let temp = heap[i]
            heap[i] = heap[i / 2]
            heap[i / 2] = temp
            i = i / 2
        }
    }
    
    /// 小顶堆的从上往下堆化
    /// - Parameters:
    ///   - index: 要堆化数据的下标
    ///   - heap: 做堆化处理的数组
    ///   - capacity: 数组中有效数据的个数
    class func minTopHeapify(fromTop index: Int, heap: inout [HeapNode], capacity: Int) {
        var i = index
        var maxPos = i
        while true  {
            if 2 * i <= capacity && heap[2 * i].value <= heap[i].value {
                maxPos = 2 * i
            }
            if 2 * i + 1 <= capacity && heap[2 * i + 1].value <= heap[maxPos].value{
                maxPos = 2 * i + 1
            }
            if i == maxPos {// 比自己的子节点小，或者没有子节点了
                break
            }
            // 交换
            let temp = heap[i]
            heap[i] = heap[maxPos]
            heap[maxPos] = temp
            i = maxPos
        }
    }
    
    /// 建堆 -在原数组中操作，先在数组最前面插入一个空节点，
    /// 然后从角标1开始，假设它为堆的最后一个叶子节点，对他进行从下往上堆化，完成一次堆化后，
    /// 角标跳到2，进行同样的操作，一直到数组中的所有元素都堆化一遍，最后得到的就是一个小顶堆
    /// - Parameter arr: 需要堆化的数组
    class func create(fromFirst arr:inout [HeapNode]){
        let number = arr.count // 遍历次数
        arr.insert(HeapNode(-1), at: 0)
        var i = 0
        while i < number {
            i += 1
            minTopHeadify(fromBottom: i, heap: &arr)
        }
    }
    
    // 删除堆顶元素
    class func deletTop(_ arr: inout [HeapNode]) {
        var capacity = arr.count - 1 // 第一个元素不算入堆的空间
        if capacity == 0 {
            return
        }
        
        if capacity == 1 {
            arr.remove(at: 1)
            return
        }
        
        // 将最后一个子节点赋值到堆顶，并删除最后一个子节点
        arr[1] = arr[capacity]
        arr.remove(at: capacity)
        capacity -= 1
        // 从上往下堆化
        minTopHeapify(fromTop: 1, heap: &arr, capacity: capacity)
    }
    
}
